1. Field of the Invention
The present invention relates to user interfaces for data storage and retrieval systems and more particularly to a system and method for choosing and executing queries to such data storage and retrieval systems and traversing databases associated therewith.
2. Description of Related Art
Many current data storage and retrieval systems are organized using a principle commonly identified as "hypertext". Hypertext has resulted as computer work stations and digital storage have grown cheaper, more powerful and more available. It has become increasingly more attractive to extend the traditional notion of "flat" text files organized hierarchically by allowing more complex nonlinear organizations of material. In a hypertext system, each data entity, i.e. document or node, may be directly connected to other documents in the system by pointers, or links. The human user of a hypertext system moves between (browses) documents by following these links.
An essential characteristic of a hypertext database system is a machine supported ability to efficiently traverse via these links from node to node. In this regard, as noted in the article entitled "Hypertext: An Introduction and Survey" by J. Conklin, COMPUTER, September 1987, pages 17-41, to qualify as hypertext, a system should require no more than a couple of keystrokes (or mouse movements) from the user to follow a single link. The links provided by the interface transport the user quickly and easily to a new place in the hypertext system. Another characteristic of a hypertext system is the speed with which the system responds to referencing requests. Only brief delays typically occur (one or two seconds at most).
Although hypertext systems presently provide the ability for the user to traverse efficiently between nodes via links once he or she determines the desired links to be utilized, the number of documents in a hypertext system may be very large. Consequently, the number of links connected to any document may also become very large. This leads to difficulties in "navigating" through the database, the large number of links from each document often resulting in confusion by the user when attempting to select which link to follow.
One attempt to overcome this problem is by providing an overview display or "map" of the hypertext documents and links. This technique has the disadvantage of creating a large and complex map display when the number of documents and links is large. There is a resultant need for further control and display options which the user must learn, and in the expenditure of the user's time in manipulating the map, rather than more effective use of his time, such as reading documents.
Another solution to this navigational dilemma is to apply standard database search and query techniques for locating documents which the user is seeking. This involves addressing entities by content; that is, by text or numbers stored, in addition to or rather than a user-assigned name or symbol. This is usually executed by applying some combination, using boolean operations of key word and full string search and predicates on other attributes (such as author, time of creation, type, etc.) of nodes or links. Various standard and proprietary languages exist for querying structured databases or text retrieval systems (for example, DIALOG, SQL). All of these languages share the drawback of being arbitrary and complex, which poses a problem in applications where untrained users must query a data storage system, or in educational and training uses where presuming prior user training in the query method is inappropriate.
Experience with textual query methods has also shown that they are subject to tradeoffs between precision (the number of retrieved entities which are actually interesting) and recall (the fraction of total interesting entities which are actually found). Such studies have found that, for instance, a typical query to a legal information system produces only 20% of those database entities which are actually relevant. (See the article entitled "An Evaluation of Retrieval Effectiveness for a Full Text Document Retrieval System", by D. C. Blair and M. E. Maron, COMMUNICATIONS OF THE ACM, March 1985, Vol. 28, No. 3, Pgs. 289-299.)
Other attempts to control the complexity of linking have concentrated on database-wide elision of sets of links. For instance, the Intermedia system allows the separation of links into sets called webs. Only one of these sets is visible to the user at a time. This achieves simplification but at the expense of possibly removing valuable links from consideration if those links are stored in the webs which are not loaded. (See the article entitled "Intermedia: The Concept and the Construction of a Seamless Information Environment", by N. Yankelovich, et.al., COMPUTER, January 1988, pgs. 81-96.)
Another approach to elision is filtering, that is, database-wide selection of documents and links based on a query, in a fashion similar to that described above. In some systems (e.g. see the article entitled "Super Book: An automatic tool for information exploration--hypertext?", by J. R. Remde, et al., Bell Communications Research, HYPERTEXT '87 PAPERS, November 1987, pgs. 175-188; and the article entitled "Searching for Information in a Hypertext Medical Handbook", COMMUNICATIONS 0F THE ACM, July 1988, pgs. 880-886), the pattern of links is also considered in the decision to remove entities from the user's view. However, because such filtering methods treat the entire database at once, they share the limit of precision--recall tradeoff as described above, meaning that they achieve reduction of complexity at the expense of loss of information.
With the growing use of multimedia databases containing not only textual documents, but also data entities containing sound and graphics, and the growing utilization of hypertext-type nodal networks within these multimedia databases, the requirement for effective and meaningful navigation has become even more imperative.
Utilization of a hypertext-type nodal network in conjunction with a multimedia database may be described as a "hypermedia database". Thus, as defined broadly herein, the term "hypermedia system" refers to a database which may be constructed to include documents or nodes and machine supported selected linkages or pointers which provide the user with the ability to efficiently travel from one node to another. These nodes may include text, sound, or graphic material. An example of a system that supports hypermedia is Apple Computer Inc.'s system sold under the trademark "HYPERCARD" which allows traversal through a hypertext-type nodal network containing text, sound and graphics. HYPERCARD provides the machine supported ability to selectively traverse in an automatic fashion via linkages, from one item to another, the items being selectively linked to each other in the nodal network.
In attempting to develop improved techniques for browsing through mature HYPERCARD databases, the present inventors have discovered the novel system and method of the present invention. As will be disclosed below, an aspect of the present invention involves a process for selecting, ordering and displaying a subset of the possible links from a document, resulting in reduced user confusion while browsing through a hypermedia system. Another aspect of the inventive technique involves the use of an intuitive representation to the user of options or "guides", the selection thereof effectively masking a complex indexing and query method.